#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
using std::unordered_map;
using std::vector;
using std::string;
using std::sort;


class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<int>> map;
        for (int i = 0; i < strs.size(); i++) {
            auto k = key(strs[i]);
            if (map.find(k) == map.end()) {
                map.insert({k, {i}});
            }
            else {
                map.at(k).push_back(i);
            }
        }

        vector<vector<string>> results = {};
        for (auto k : map) {
            vector<string> a;
            for (auto i: k.second) a.push_back(strs[i]);
            results.push_back(a);
        }
        return results;
    }

    string key(string s) {
        sort(s.begin(), s.end());
        return s;
    }
};